Learning with Privacy at Scale翻译

正在看Apple发布的“Learning with Privacy at Scale”,人工翻译了一下：

Abstract 获得能够提升用户体验的数据涉及隐私，团队设计系统通过局部差分隐私完成大规模学习，数据来源流行emoji，流行健康数据类型，safari媒体回放。

Introduction 数据是个人且敏感的，必须保持隐私。此外，使用该数据的系统必须考虑总资源、计算成本、通信成本。本系统既解决隐私又解决实际运用的相关问题。 差分隐私提供了隐私的严格数学定义，是当下隐私的最强保证。在差分隐私的框架中，有两种设定：中心和局部。本团队不收集服务器的源数据，那是中心差分隐私需要的，而是使用更高级的局部差分隐私，其优点在于数据被设备发送前已经打乱，所以服务器无法看到或接收到源数据。 我们的系统是事先同意并且透明的。数据以平均水平差分隐私加密，此外，本团队限制被加密事件每case传输的数量。传输过程每天通过加密通道完成，无设备识别。记录到达一个访问受限的服务器，在这里IP识别被立刻废除，任何记录间的联系同样被废除。此时，我们无法分辨，2记录是否来自同一用户，这些记录用来计算相关数据。 本团队关注于计算元素出现的频次，从而我们考虑2个问题：1、从已知元素目录计算频次；2、元素目录未知，想要获得数据库中频次最高的元素列表。我们的主要工作： 1、设计了一个系统，使用局部差分隐私，结合已有的隐私案例。 2、设计了全新的差分隐私算法计算目录已知和未知条件下的元素频次。 3、分析了权衡表达式，包含隐私、实用、计算量和设备带宽。 4、在上百万设备中使用该算法，得到不同case下的结果。 5、

Related Work 差分隐私10年前起源于密码学和理论计算机研究，已经成为隐私基准。大多数研究使用中心差分隐私，一个可信任的实体储存所有源数据，然后以差分隐私的方式释放总和数据，本文专注于更强的隐私类型——局部差分隐私。 Bassily和Smith提出了一种局部差分隐私算法，以获得数据库中最高频次项和频次数据库，实现了理论小错误、低计算量和低通信成本。此前，一系列工作试图减少时间和空间复杂度的同时保持理想的错误度，但是受困于一个与群大小相关的多项式的运行时间，这些工作中的实用性分析设置参量，在最差的case下实现渐近理想实用，但是如果参数不是按照规定方式设置，实用性不能保证达到最佳，因此，如果服务器计算或者设备带宽能够增加，这样做并不能导致更高的实用性。 RAPPOR在Chrome上使用局部差分隐私，我们描述第一个大型差分隐私实践中的终端-终端细节。此外，我们设计算法和表达式，以计算如何权衡隐私、准确度、传输成本、通信成本。相对于RAPPOR，我们的实用性理论给出了选择这些算法参量的规范方法。 此外，为了保证传输成本在最小值，我们的Hadamard Count Mean Sketch算法能够在用户仅仅发送一个加密字节时计算准确次数。

Background and System Overview 3.1 Differential Privacy Definition1: Local Randomizer 隐私参量ε捕捉来自算法输出的隐私丢失，ε= 0，完美隐私，输出和输入完全不相关；ε=∞，无隐私保证。 差分隐私运用于大于1的输入数据库，在局部差分隐私模型中，算法仅仅获得通过本地随机后的数据，因此服务器中不存储源数据。

Definition2: Local Differential Privacy

3.2 System Architecture 我们的系统包含设备端和服务器端的数据处理：在设备端，源数据保证通过差分隐私加密；访问限制的服务器进行数据处理，这些数据将进入吸收和汇总部分。

3.2.1 Privatization 我们定义每个事件的隐私参数ε，此外，我们限制每个case每天能够传输的加密的记录。我们提供额外的隐私，通过擦除服务器处的用户识别和IP地址，在服务期处，记录按case分开，所以记录间没有联系。 无论何时，一个事件发生了，数据通过局部差分隐私加密，并存储在设备上，而不是立刻传输给服务器。在依设备情况而定的时延之后，系统随机地从差分隐私记录中取样，并把取样记录发送给服务器，这些记录不包含设备识别或事件发生的时间标记。设备与服务器之间通信的加密使用TLS.

3.2.2 Ingestion and Aggregation 机密的数据进入吸收器之前首先被剥除IP地址，然后吸收器从所有用户中收集数据并批量处理，批量处理移除时间标记，并将这些记录按照case分类。此外，吸收器在每种case下打乱加密数据的顺序，然后将输出推至下一步骤。 汇总器从收集器中获得加密记录，并且在每个case下生成1个差分隐私的直方图，多个case的数据不会混合。在这些直方图中，只有频次超过阈值的元素才会被记录。

4 Algorithm 算数sketch算法与我们的算法相关，该算法从数据流中获得多次记录的元素，并获得其准确次数，我们同样使用sketch矩阵数据结构计算一系列加密元素。然而，为了保证差分隐私，我们的算法严重偏离。

4.1 Private Count Mean Sketch CMS算法包含了用户端算法和服务器端算法。用户端算法保证了离开用户设备的数据是ε-差分隐私保护的，此外，该算法保证传输的是合理大小，通过完成元素和散列函数之间的映射。 首先，独立选择1组包含k个散列函数的随机组合，随后，这个散列函数组合在用户端和服务器端被分享，最后，实用性分析是ε，m,k的函数。

4.1.1 Client-Side Algorithm 加密的向量和指数被送往服务器。 隐私分析显示Client-Side Algorithm是ε局部随机器，既然服务器对来自用户的加密数据仅仅使用一个后处理函数，因此，保证Client-Side Algorithm是ε局部随机器就保证CMS是ε差分隐私保护的。

Theorem4.1(Privacy guarantee)：保证Client-Side Algorithm是ε局部随机器就保证CMS是ε差分隐私保护的。

4.1.2 Server-Side Algorithm

5 Balancing Utility, Privacy, Computation and Communication Overhead 我们想要保证我们的系统和算法适用于上百万使用iOS和macOS设备的用户，为此，我们提供了方法权衡实用性和隐私预算、设备带宽、服务器计算成本。然后，我们描述了一个系统的方式以实施差分隐私算法，该算法能够实现好的实用性和隐私。为了透明化，我们使得传输给苹果服务器的加密数据在用户设备上也可见。 当前最先进的局部差分隐私算法能够解决已知和未知目录问题，在渐近无限小带宽和计算成本的条件下，通过使用JL转换。然而，对实用性的影响不清楚，如果设备带宽和服务器计算量和规定值不同。 我们算法CMS和HCMS最大的好处在于它们给我们超曲面，在超曲面中，我们可以看到我们计算错误的均衡，比如说，当我们减半设备带宽。在HCMS中，设备仍然可以传输单个字节给服务器，并且我们可以通过增加参数m从而减少方差，这仅仅影响服务器的计算成本。 我们的实施从总体隐私报告中得到了高实用性。此外，我们可以看到实用性、隐私、服务器计算量和设备带宽间的权衡。 我们现在可以分析每个参数是如何影响被计算次数的方差的。参数m决定了对于用户的设备带宽，然而参数k直接影响了服务器运行时间。随后，我们可以画出次数的标准差以ε、设备带宽成本、服务器运行时间为自变量的函数变化，以观察多个因素之间的权衡。

6 Results 我们在上百万台设备上实施了我们的算法，我们展示以下使用案例的结果：新词、流行emoji、Safari上的视频回放、Safari上高能量和存储使用和流行健康知识的使用。

6.1 Discovering New Words 我们想要学习设备上字典没有的词从而改良自动修正功能。为了发现新单词，我们实施了SFP算法。 本算法产生了横跨多种语言的结果，包括英语、法语和西班牙语。比如说，从英语键盘中学习到的语言可以被分为几种目录：缩略，比如wyd, wbu, idc；流行表达，比如bruh, bun, bae, tryna；季节性或者趋势单词，比如Mayweather, McGregor, Despacito, Moana, Leia； 外来词，比如dia, queso, aqui, jai. 使用数据，我们不断地更新设备上的词典以改进键盘体验。 另一个单词的类别是没有后尾的单词。如果用户意外地敲击了可预测的最容易剩下的单元，包括目前已知的字符串，一个空格会被加入他们现在的单词，而不是他们想打的字母。这是一个关键的理解，从而我们能够根据我们的局部差分隐私算法学习。

6.2 Discovering Popular Emojis 已知我们用户数据库emoji的流行度，我们想要确定具体哪个emoji被用户最常使用，以及这些特点的相对分布。为此，我们在不同的场景实施我们的算法，从而去理解键盘上emoji的分布。 有了这些数据，我们看到不同键盘场景有着许多不同，我们看到来自2个场景的快照： 英语和法语。使用这些数据，我们可以改善不同场景下预测emoji 快速敲打。

6.3 Safari Auto-play Intent macOS上的safari使用户能够浏览网页被更少地分心，特别是以从有声自动播放网页中脱离的方式。 我们能够以算法的形式推断违约自动播放政策，根据众包参与标尺。Safari决定一个用户可能想要有声自动播放，如果用户播放的媒体元素最初是被禁止自动播放的，或者当媒体元素被允许自动播放是被允许继续的。我们仅仅搜集加密的域名，而不是全URL. 在这些报道中，我们使用我们的CMS算法，D是所有可能网站域名，而目录是一系列250000个网页域名。注意到，我们是把一个大量的网页域名（250000）映射到一个显著更小的空间（1024bits），所以可预测将会有许多的散列合并，这提供了对于原记录更远的否定。使用差分隐私，我们能够成功地识别紧密更新的网页集，这些网页大多数用户更倾向于有声自动播放，比如流服务，比如MOOC和其他流行视频网站。

6.4 Identifying High Energy and Memory Usage in Safari 一些网站过于资源密集，我们希望识别这些网站，从而保证一个更佳的用户体验。我们考虑2种域名：造成高内存使用的和由于CPU使用造成高能量损耗的。在iOS11和macOS上，safari自动地可以探测这些特别的域名，并且使用差分隐私报告这些。 使用我们的算法，我们可以确定哪个域名有高资源消耗。回忆，HCMS的差分隐私记录只有1bit. 我们的数据显示消耗最高的域名包括视频消费网站、购物网站和新闻网站。

6.5 Understanding HealthKit Usage 我们想要知道流行的健康数据类型从而推进Health app未来的改进。然而，健康数据是敏感的，比如说，如果用户记录血糖水平，这可能意味着用户有过度肥胖。我们使用CMS去发现最流行的健康数据。 我们的发现显示睡眠分析，心率，动态卡路里，生殖健康和心理状态是最流行健康记录。

7 Conclusion 本文，我们展现了一个新奇的学习系统算法，它使用局部差分隐私算法并且与隐私的最好实践相结合。为了将我们的系统推广给上百万的用户和多种案例，我们为已知和未知目录情况都建立了差分隐私算法：CMS, HCMS, SFP. 我们已经提供了权衡多种因素的分析表达式，包括隐私、实用性、服务器计算量和设备带宽。我们的实用性理论提出了一个理论方法去选择算法参量从而在不减小准确度的条件下最小化用户的传输损耗。没有这样的表达式，评价对准确性的影响是困难的，比如，如果传输损耗通过不进行高成本的迭代减少传输成本。此外，为了保证传输损耗在一个绝对的最小值，我们的HCMS算法可以获得准确的计算在每个用户仅仅发送单个加密的字节。我们相信这篇论文是第一之一展示差分隐私在实际生活多种案例下的成功应用。我们显示我们可以找到流行的缩写和打出的俚语，流行的emoji，流行的健康数据类型同时满足局部差分隐私。此外，我们可以识别消耗太多能量或者内存的网页和用户想要自动播放的网页。这些信息可以并且已经被用于提升特性为了用户体验。 我们希望这篇文章可以起到连接隐私领域理论和实践的桥梁。我们同样相信我们的工作将会持续地支撑许多大范围学习的问题，这些问题被解决的同时是保护用户隐私的。